%% main.tex --- файл-обертка для диплома

\documentclass[russian,utf8,simple,floatsection,equationsection]{eskdtext} 
\include{defs}  % вставляем содержимое служебных инструкций из defs.tex

\setcounter{section}{3}

\ESKDcolumnII{\normalsize{Проектирование и разработка алгоритмов и структур данных}}

\begin{document}
\section{Проектирование и разработка алгоритмов и структур данных.}

\subsection{Проектирование базы данных}
\subsubsection{Концептуальная схема }

Реляционная модель данных в подавляющем большинстве случаев вполне
достаточна для моделирования любых данных. Однако проектирование базы
данных в терминах схемы отношений на практике может вызвать большие
затруднения, т.к. в этой модели изначально не предусмотрены механизмы
описания семантики предметной области. С этим связано появление
семантических моделей данных, которые позволяют описать конкретную
предметную область гораздо ближе к интуитивному пониманию и, в то же
время, достаточно формальным образом.


Часто семантическое моделирование используется только на первой стадии
проектирования базы данных. Концептуальная схема будущей БД строится
на основе некоторой семантической модели, а затем вручную
преобразуется к реляционной схеме.


Существуют методики, четко описывающие все этапы такого преобразования.

При таком подходе отсутствует потребность в дополнительных программных
средствах, поддерживающих семантическое моделирование. Требуется
только владение основами выбранной семантической модели и правилами
преобразования концептуальной схемы в реляционную.

Следует заметить, что многие начинающие проектировщики баз данных
недооценивают важность семантического моделирования вручную. Зачастую
это воспринимается как дополнительная и излишняя работа. Эта точка
зрения абсолютно неверна. Во-первых, построение мощной и наглядной
концептуальной схемы БД позволяет более полно оценить специфику
моделируемой предметной области и избежать возможных ошибок на стадии
проектирования схемы реляционной БД. Во-вторых, на этапе
семантического моделирования производится важная документация (хотя бы
в виде вручную нарисованных диаграмм и комментариев к ним), которая
может оказаться очень полезной не только при проектировании схемы
реляционной БД, но и при эксплуатации, сопровождении и развитии уже
заполненной БД.

Концептуальная схема данных представлена на рисунке~\ref{db_concept}.

\begin{figure}[!hb]
  \centering
  \includegraphics[angle=0, width=\textwidth]{db_concept}
  \caption{Концептуальная схема базы данных.}
  \label{db_concept}
\end{figure}

Сущности, представленные на диаграмме:
\begin{enumerate}
\item ГА - параметры запуска генетического алгоритма;
\item Отчет - отчет о работе;
\item XP - данные эксперимента;
\item Result - результат прогнозирования;
\item Param - параметры графика.
\end{enumerate}

\subsubsection{Системный анализ}
Следующим этапом разработки программного обеспечения является
проектирование базы данных.

Основными этапами проектирования базы данных являются:
\begin{itemize}
\item системный анализ;
\item Инфологическое проектирование;
\item логическое проектирование.
\end{itemize}

Сутью системного анализа является определение задач, которые решаются
в системе и для кого. Представим объекты системы:
\begin{itemize}
\item Параметры работы ГА;
\item Параметры отчета;
\item Результаты эксперимента;
\item Результат прогнозирование.
\end{itemize}

Атрибутами параметров ГА являются:
\begin{itemize}
\item Размер популяции;
\item Вероятность мутации;
\item Минимальное значение фитнесса для остановка;
\item Процент отбора.
\end{itemize}

Атрибутами отчета являются:
\begin{itemize}
\item Цвет графика;
\item Тип каждой линии;
\item Легенда;
\item Данные эксперимента, по которому построен график.
\end{itemize}

Атрибутами <<результаты эксперимента>> являются:
\begin{itemize}
\item Матрица входных параметров эксперимента;
\item Вектор выходных значений.
\end{itemize}

Атрибутами <<результаты апроксимации>> являются:
\begin{itemize}
\item Количество правил;
\item Параметры функций принадлежности.
\end{itemize}

\subsubsection{Инфологическое проектирование}
Инфологическая модель применяется на втором этапе проектирования БД,
то есть после словесного описания предметной области. При разработке
серьезных корпоративных информационных систем проект базы данных
является тем фундаментом, на котором строится вся система в
целом. Следовательно, инфологическая модель должна включать такое
формализованное описание предметной области, которое легко будет
<<читаться>> не только специалистами по базам данных, и это описание
должно быть настолько емким, чтобы можно было оценить глубину и
корректность проработки проекта БД, и конечно оно не должно быть
привязано к конкретной СУБД. Инфологическое проектирование, прежде
всего, связано с попыткой представления семантики предметной области в
модели БД. Реляционная модель данных в силу своей простоты и
лаконичности не позволяет отобразить семантику, то есть смысл
предметной области. Ранние теоретико-графовые модели в большей степени
отображали семантику предметной области. Они в явном виде определяли
иерархические связи между объектами предметной области. Проблема
представления семантики давно интересовала разработчиков, и в
семидесятых годах было предложено несколько моделей данных, названных
семантическими моделями. К ним можно отнести семантическую модель
данных, предложенную Хаммером (Hammer) и Мак-Леоном (McLean) в 1981
году, функциональную модель данных Шипмана (Shipman), также созданную
в 1981 году \red{[5]}, модель <<сущность-связь>>, предложенную Ченом (Chen) в
1976 году, и ряд других моделей. У всех моделей были свои
положительные и отрицательные стороны, но испытание временем выдержала
только последняя. И в настоящий момент именно модель Чена
<<сущность-связь>>, пли <<Entity Relationship>>, стала фактическим
стандартом при инфологическом моделировании баз данных. Общепринятым
стало сокращенное название ER-модель, большинство современных
CASE-средств содержат инструментальные средства для описания данных в
формализме этой модели. Кроме того, разработаны методы автоматического
преобразования проекта БД из ER-модели в реляционную, при этом
преобразование выполняется в дата-логическую модель, соответствующую
конкретной СУБД. Все CASE-системы имеют развитые средства
документирования процесса разработки БД, автоматические генераторы
отчетов позволяют подготовить отчет о текущем состоянии проекта БД с
подробным описанием объектов БД и их отношений, как в графическом
виде, так и в виде готовых стандартных печатных отчетов, что
существенно облегчает ведение проекта.  

В настоящий момент не существует единой общепринятой системы
обозначений для ER-модели и разные CASE-системы используют разные
графические нотации, но разобравшись в одной, можно легко понять и
другие нотации \red{[5]}.

\emph{Модель <<сущность—связь>>}

Модель Сущность-Связь (ER-модель) (англ. entity-relationship model или
entity-relationship diagram ) — это модель данных, позволяющая
описывать концептуальные схемы. Она предоставляет графическую нотацию,
основанную на блоках и соединяющих их линиях, с помощью которых можно
описывать объекты и отношения между ними какой-либо другой модели
данных. В этом смысле ER-модель является мета-моделью данных, то есть
средством описания моделей данных. Как любая модель, модель
<<сущность—связь>> имеет несколько базовых понятий, которые образуют
исходные кирпичики, из которых строятся уже более сложные объекты по
заранее определенным правилам. Эта модель в наибольшей степени
согласуется с концепцией объектно-ориентированного проектирования,
которая в настоящий момент, несомненно, является базовой для
разработки сложных программных систем \red{[6]}.

В основе ER-модели лежат следующие базовые понятия:
Сущность имеет имя, уникальное в пределах моделируемой системы. Так
как сущность соответствует некоторому классу однотипных объектов, то
предполагается, что в системе существует множество экземпляров данной
сущности. Объект, которому соответствует понятие сущности, имеет свой
набор атрибутов — характеристик, определяющих свойства данного
представителя класса. При этом набор атрибутов должен быть таким,
чтобы можно было различать конкретные экземпляры сущности. Например, у
сущности Сотрудник может быть следующий набор атрибутов: табельный
помер, фамилия, имя, отчество, дата рождения, количество детей. Набор
атрибутов, однозначно идентифицирующий конкретный экземпляр сущности,
называют ключевым. Для сущности Сотрудник ключевым будет атрибут
табельный номер, поскольку для всех сотрудников данного предприятия
табельные номера будут различны. Экземпляром сущности Сотрудник будет
описание конкретного сотрудника предприятия. Одно из общепринятых
графических обозначений сущности - прямоугольник, в верхней части
которого записано имя сущности, а ниже перечисляются атрибуты. Между
сущностями могут быть установлены связи - бинарные ассоциации,
показывающие, каким образом сущности соотносятся или взаимодействуют
между собой. Связь может существовать между двумя разными сущностями
пли между сущностью и ей же самой (рекурсивная связь). Она показывает,
как связаны экземпляры сущностей между собой. Если связь
устанавливается между двумя сущностями, то она определяет взаимосвязь
между экземплярами одной и другой сущности. Например, если у пас есть
связь между сущностью <<Студент>> и сущностью <<Преподаватель>> и эта
связь — руководство дипломными проектами, то каждый студент имеет
только одного руководителя, но один и тот же преподаватель может
руководить множеством студентов-дипломников. Поэтому это будет связь
<<один-ко-многим>> (1:$\infty$), один со стороны <<Преподаватель>> и многие со
стороны <<Студент>>. Связи делятся на три типа по множественности:
один-к-одному (1:1), один-ко-многим (1:$\infty$), многие-ко-многим
($\infty$:$\infty$). Связь один-к-одному (1:1) означает, что экземпляр одной
сущности связан только с одним экземпляром другой сущности. Связь (1:
$\infty$) означает, что один экземпляр сущности, расположенный слева по
связи, может быть связан с несколькими экземплярами сущности,
расположенными справа по связи. А связь <<многие-ко-многим>> ($\infty$:$\infty$)
означает, что один экземпляр первой сущности может быть связан с
несколькими экземплярами второй сущности, и наоборот, один экземпляр
второй сущности может быть связан с несколькими экземплярами первой
сущности.  

Между двумя сущностями может быть задано сколько угодно связей с
разными смысловыми нагрузками.

На основе этих данных опишем сущности, присутствующие в базе данных.

Сущность <<параметров ГА>>.
Атрибутами являются:
\begin{itemize}
\item id
\item Размер популяции;
\item Вероятность мутации;
\item Минимальное значение фитнесса для остановка;
\item Процент отбора.
\end{itemize}

Сущность <<Отчет>>
Атрибутами являются:
\begin{itemize}
\item id;
\item Цвет графика;
\item Тип каждой линии;
\item Легенда;
\item Данные эксперимента, по которому построен график.
\end{itemize}

Сущность <<результаты эксперимента>>.
Атрибутами  являются:
\begin{itemize}
\item id;
\item Матрица входных параметров эксперимента;
\item Вектор выходных значений.
\end{itemize}

Атрибутами <<результаты аппроксимации>> являются:
\begin{itemize}
\item id;
\item Количество правил;
\item Параметры функций принадлежности.
\end{itemize}

В результате построения модели предметной области в виде набора
сущностей и связей получаем связный граф.

\subsubsection{Логическое проектирование}

Схемы базы данных представлена на рисунке~\ref{db} 

\begin{figure}[!ht]
  \centering
  \includegraphics[angle=0, width=\textwidth]{db}
  \caption{ER диаграмма базы данных.}
  \label{db}
\end{figure}

Для создания этих таблиц, использовались следующие SQL запросы: 

\begin{lstlisting}[language=SQL]
CREATE TABLE IF NOT EXISTS GA (
	id BIGINT NOT NULL  AUTO_INCREMENT,
	size FLOAT NOT NULL,
	mutation_rate  FLOAT NOT NULL,
	PRIMARY KEY (id)
	);
\end{lstlisting}
Таблица GA – содержит описание ГА:
\begin{description}
\item[size] - размер популяции;
\item[mutation\_rate] - вероятность мутации;
\end{description}

\begin{lstlisting}[language=SQL]
CREATE TABLE IF NOT EXISTS Report (
	id BIGINT NOT NULL  AUTO_INCREMENT,
	colour INT NULL,
	line_type CHAR(3) NOT NULL,
        legend CHAR(255) NOT NULL,
        xp BIGINT NOT NULL,
        ga BIGINT NOT NULL,
        result BIGINT NOT NULL,
	PRIMARY KEY (id),
	FOREIGN KEY(xp)  REFERENCES XP (id),
        FOREIGN KEY(ga)  REFERENCES GA (id),
        FOREIGN KEY(result)  REFERENCES Result (id),
	);
\end{lstlisting}
Таблица Report – содержит описание отчета:

\begin{description}
\item[colour] - цвет графика;
\item[line\_type] - тип линии;
\item[legend] - легенда;
\item[xp] - результаты эксперимента;
\item[ga] - ГА;
\item[result] - результаты.
\end{description}

\begin{lstlisting}[language=SQL]
CREATE TABLE IF NOT EXISTS XP (
	id BIGINT NOT NULL  AUTO_INCREMENT,
	data BIGINT NOT NULL,
	PRIMARY KEY (id),
        FOREIGN KEY(data)  REFERENCES data (id),
	);
\end{lstlisting}
Таблица XP – содержит описание данных эксперимента:
\begin{description}
\item[data] - данные;
\end{description}

\begin{lstlisting}[language=SQL]
CREATE TABLE IF NOT EXISTS Data (
	id BIGINT NOT NULL  AUTO_INCREMENT,
	x BIGINT NOT NULL,
        y BIGINT NOT NULL,
	PRIMARY KEY (id),
	);
\end{lstlisting}
Таблица Data – содержит описание данных эксперимента:
\begin{description}
\item[x] - значение X;
\item[y] - значение y;
\end{description}

\begin{lstlisting}[language=SQL]
CREATE TABLE IF NOT EXISTS Result (
	id BIGINT NOT NULL  AUTO_INCREMENT,
	rules_count INT NOT NULL,
	params BIGINT NOT NULL,
	PRIMARY KEY (id),
        FOREIGN KEY(params)  REFERENCES Param (id),
	);
\end{lstlisting}
Таблица Result – содержит описание результаты аппроксимации:
\begin{description}
\item[rules\_count] - количество правил;
\item[params] - параметры функций принадлежности.
\end{description}

\begin{lstlisting}[language=SQL]
CREATE TABLE IF NOT EXISTS Param (
	id BIGINT NOT NULL  AUTO_INCREMENT,
	c BIGINT NOT NULL,
        q BIGINT NOT NULL,
	PRIMARY KEY (id),
	);
\end{lstlisting}
Таблица Param – содержит описание результаты аппроксимации:
\begin{description}
\item[c] - параметр c;
\item[q] - параметры q.
\end{description}

\subsection{Проектирование диаграммы классов}

UML (сокр. от англ. Unified Modeling Language — унифицированный язык
моделирования) — язык графического описания для объектного
моделирования в области разработки программного обеспечения. UML
является языком широкого профиля, это открытый стандарт, использующий
графические обозначения для создания абстрактной модели системы,
называемой UML моделью. UML был создан для определения, визуализации,
проектирования и документирования в основном программных систем. UML
не является языком программирования, но в средствах выполнения
UML-моделей как интерпретируемого кода возможна кодогенерация.

Использование UML не ограничивается моделированием программного
обеспечения. Его также используют для моделирования бизнес-процессов,
системного проектирования и отображения организационных структур.

UML позволяет также разработчикам программного обеспечения достигнуть
соглашения в графических обозначениях для представления общих понятий
(таких как класс, компонент, обобщение (generalization), объединение
(aggregation) и поведение) и больше сконцентрироваться на
проектировании и архитектуре.

В 1994 году Гради Буч и Джеймс Рамбо, работавшие в компании Rational
Software, объединили свои усилия для создания нового языка
объектно-ориентированного моделирования. За основу языка ими были
взяты методы моделирования, разработанные Бучем (Booch) и Рамбо
(Object-Modeling Technique — OMT). OMT был ориентирован на анализ, а
Booch — на проектирование программных систем. В октябре 1995 года была
выпущена предварительная версия 0.8 унифицированного метода
(англ. Unified Method). Осенью 1995 года к компании Rational
присоединился Айвар Якобсон, автор метода Object-Oriented Software
Engineering — OOSE. OOSE обеспечивал превосходные возможности для
спецификации бизнес-процессов и анализа требований при помощи
сценариев использования. OOSE был также интегрирован в унифицированный
метод.

На этом этапе основная роль в организации процесса разработки UML
перешла к консорциуму OMG (Object Management Group). Группа
разработчиков в OMG, в которую также входили Буч, Рамбо и Якобсон,
выпустила спецификации UML версий 0.9 и 0.91 в июне и октябре 1996
года.

На волне растущего интереса к UML к разработке новых версий языка в
рамках консорциума UML Partners присоединились такие компании, как
Digital Equipment Corporation, Hewlett-Packard, i-Logix, IntelliCorp,
IBM, ICON Computing, MCI Systemhouse, Microsoft, Oracle Corporation,
Rational Software, Texas Instruments и Unisys. Результатом совместной
работы стала спецификация UML 1.0, вышедшая в январе 1997 года. В
ноябре того же года за ней последовала версия 1.1, содержавшая
улучшения нотации, а также некоторые расширения семантики.

Последующие релизы UML включали версии 1.3, 1.4 и 1.5, опубликованные,
соответственно в июне 1999, сентябре 2001 и марте 2003 года.

Формальная спецификация последней версии UML 2.0 опубликована в
августе 2005 года. Семантика языка была значительно уточнена и
расширена для поддержки методологии Model Driven Development — MDD
(англ.).

UML 1.4.2 принят в качестве международного стандарта ISO/IEC
19501:2005.

Диаграмма классов, Class diagram — статическая структурная диаграмма,
описывающая структуру системы, она демонстрирует классы системы, их
атрибуты, методы и зависимости между классами.

Существуют разные точки зрения на построение диаграмм классов в
зависимости от целей их применения:

\begin{itemize}
\item концептуальная точка зрения — диаграмма классов описывает модель
  предметной области, в ней присутствуют только классы прикладных
  объектов;
\item точка зрения спецификации — диаграмма классов применяется при
  проектировании информационных систем;
\item точка зрения реализации — диаграмма классов содержит классы,
используемые непосредственно в программном коде (при использовании
объектно-ориентированных языков программирования).
\end{itemize}

Диаграмма разработанной системы представлена на
рисунке~\ref{fig:uml-diagram}.

\begin{figure}[!ht]
  \centering
  \includegraphics[angle=0, width=\textwidth]{uml-diagram}
  \caption{UML диаграмма разработанной системы}
  \label{fig:uml-diagram}
\end{figure}

Класс \textbf{dna} (рисунок~\ref{dna}) является контейнером для хранения хромосомы. Он также
отвечает за сравнение приспособленности двух индивидов. Поведение
данного класса сходно с поведением класса \textbf{list}.

\begin{itemize}
\item \textbf{dna(), dna(int size),dna(dna other),dna(gvector other)}
  — конструкторы и конструкторы копирования данного класса;
\item \textbf{operator[] : double} - метод для получения \textbf{i}-го элемента
  хромосомы;
\item \textbf{operator<:bool, operator== :bool} - методы для сравнения двух
  объектов класса dna. Критерием сравнения является значение
  фитнесса. Приспособленность тем лучше, чем меньше ее значение;
\item \textbf{operator*:dna,operator+=():dna,operator/:dna} - методы,
  позволяющие  использовать данный класс как вектор. Данные операции
  не деструктивны;
\item \textbf{m\_ftn} — значение меры приспособленности хранимой
  хромосомы. Данный атрибут скрыт. Доступ осуществляется через методы
  \textbf{double ftn():const} и \textbf{set\_ftn()}; 
\item \textbf{genom: gvector} — хранимая хромосома. Тип
  \textbf{gvector} — это класс list. 
\end{itemize}

\begin{figure}[!ht]
  \centering
  \includegraphics[angle=0, width=0.2\textwidth]{dna}
  \caption{Класс Dna}
  \label{fig:dna}
\end{figure}

Класс \textbf{Population} (рисунок~\ref{fig:population}) является контейнером для хранения
хромосомы. Его основная задача - доступ к элементам текущей популяции,
а также хранение новых хромосом.
\begin{itemize}
\item \textbf{m\_population*: list} - хранимая
  популяция. Для оптимизации используется 2 вектора. В одном из них
  хранится текущая популяция, а в другой осуществляет запись новых значений.
\item \textbf{Best(): dna} — возвращает \textbf{dna}, хранимую в
  текущей популяции с наилучшей приспособленностью.
\item \textbf{Worst(): dna} — возвращает \textbf{dna}, хранимую в
  текущей популяции с наихудшей приспособленностью.
\item \textbf{ByIndex(int):dna} — возвращает \textbf{dna} по
  индексу. Также осуществляется проверка на выход за пределы размеров
  контейнера.
\item \textbf{IndexOfBest(): dna} — возвращает номер позиции \textbf{dna},
  хранимой в текущей популяции с наилучшей приспособленностью.
\end{itemize}

\begin{figure}[!ht]
  \centering
  \includegraphics[angle=0, width=0.3\textwidth]{Population}
  \caption{Класс Population}
  \label{fig:population}
\end{figure}

Класс \textbf{Fitness} является базовыми для всех классов, реализующих расчет
одной их модельных функций. Он является классом фанктором.

\begin{itemize}
\item \textbf{operator()(dna): double} — возвращает значения мера
  приспособленности. Данная операция не деструктивна по отношению к
  входной переменной.
\end{itemize}

Класс \textbf{Mutator} является базовым для  всех классов, реализующих
один из видов мутации. Вероятность мутации задается на
этапе создания объекта данного класса двумя параметрами: 
\textbf{vm: double} - вероятность мутации одного гена,
\textbf{delta:float} - величина изменения мутирующего гена в процентах
от его прежнего значения.

\begin{itemize}
\item \textbf{operator()(dna): dna} — возвращает новую \textbf{dna},
  после применения алгоритма мутации. Данная операция не деструктивна
  по отношению к входной переменной.
\end{itemize}

Класс \textbf{Crossover} является базовым для  всех классов, реализующих один
из видов мутации.
\begin{itemize}
\item \textbf{operator()(dna,dna): dna\_vector} — возвращает вектор
  новых dna после скрещивания двух dna. Данная операция не
  деструктивна по отношению к входной переменной.
\end{itemize}

Класс \textbf{Solution} предназначен для хранения результатов работы
алгоритма. Данный класс представляет собой тип \textbf{tuple}.

\begin{itemize}
\item \textbf{First} — содержит количество шагов, пройденное алгоритмом
\item \textbf{second} — лучшее решение, найденное алгоритмом.
\end{itemize}

Класс \textbf{Params} предназначен для хранения параметров работы
алгоритма. Он передается в конструктор объект \textbf{std\_ga}.

\begin{itemize}
\item \textbf{Mpv:dvector} - Представляет собой тип
  \textbf{list}. Вероятность мутации отдельных
  генов.
\item \textbf{mp:double} — вероятность мутации всей хромосомы. Если
  необходимо установить единую вероятность для всех генов, то вектор
  \textbf{Mpv} оставляют со значением по умолчанию.
\item \textbf{sp:float} — процент отбора пар для скрещивания в новую
  популяцию. По умолчанию значение равно 0.5
\item \textbf{psize:int} — размер популяции.
\item \textbf{get\_percent\_for(i:int):double} — возвращает
  вероятность мутации для \textbf{i}-го гена.
\end{itemize}

Класс \textbf{bin\_dna\_generator} используется для генерации новых
решений. Используется для тестов генетических алгоритмов.
\begin{itemize}
\item \textbf{Generate():dna} — возвращает новое, сгенерированное
  решение. Каждое значение генерируется случайно из заранее заданного
  диапазона.
\end{itemize}

Класс \textbf{Tree} используется для работы с программами,
представленными в виде дерева. Дерево хранится как список пар
ребер. Каждый узел представлен как индекс функции в классе--одиночке
\textbf{FunctionDB}. 

\begin{itemize}
\item \textbf{ivector numbers()const;} - Возвращает номера всех узлов
  дерева
\item \textbf{ivector nodes()const;}  - Возвращает номера всех функций
  дерева.
\item \textbf{int root()const;}  - Возвращает номер узла, который
 является корнем дерева.

\item \textbf{void set\_root(int root);} -  Устанавливает корень дерева.
\item \textbf{int add\_node(int n);} - Добавляет узел и возвращает его номер.
\item \textbf{void connect(int from,int to);} - Устанавливает соединения для двух узлов.
\item \textbf{ivector childs\_of(int n)const;} - Возвращает потомков
  для узла с номером \textbf{num}.
\item \textbf{int parent\_of(int n)const;} - Возвращает предка для
  узла с номером \textbf{num}.
\item \textbf{TermType eval(const VarMap\&var\_values);} - Вычисляет
  выражение, которое описывается данным деревом.
\item \textbf{ivector flat()const;} - Преобразует дерево в
  список. Данная операция используется для записи дерева в файл.
\item \textbf{void flat\_to\_tree(const ivector\&iv);} - Преобразует
  вектор в дерево.
\item \textbf{Tree clone()const;} - Возвращает копию текущего дерева.
\item \textbf{Tree sub\_tree(int num)const;} -  Возвращает поддерево,
  корнем которого является \textbf{index}. Используется в операторе
  скрещивания.
\item \textbf{void set\_sub\_tree(int parent,const Tree\&tree);} -
  Устанавливает узлу \textbf{parent} поддерево tree.
\item \textbf{int size()const;} - Количество улов в дереве
\item \textbf{void remove\_node(int pos);} - Удаляет узел, с номером
  \textbf{pos} включая всех его потомков.
\item \textbf{std::string to\_str()const;} - Преобразует в строку.
\item \textbf{void clear();} - Удаляет все узлы и связи из дерева.
\item \textbf{void restore\_from\_str(const std::string\&s);} -
  Преобразует из строки
\item \textbf{int get\_node\_by\_number(const int number)const;} -
  Возвращает номер узла по его номеру в дерева
\end{itemize}


\subsection{Разработка пользовательского интерфейса.}
Эргономика включается в процессы разработки и тестирования
программного продукта как часть системы качества. Разработка
пользовательского интерфейса (ПИ) ведется параллельно дизайну
программного продукта в целом и в основном предшествует его
имплементации. Процесс разработки ПИ разбивается на этапы жизненного
цикла: 
\begin{itemize}
\item Анализ трудовой деятельности пользователя, объединение
  бизнес-функций в роли. 
\item Построение пользовательской модели данных, привязка объектов к
  ролям и формирование рабочих мест. 
\item Формулировка требований к работе пользователя и выбор
  показателей оценки пользовательского интерфейса. 
\item Разработка обобщенного сценария взаимодействия пользователя с
  программным модулем (функциональной модели) и его предварительная
  оценка пользователями и Заказчиком. 
\item Корректировка и детализация сценария взаимодействия, выбор и
  дополнение стандарта (руководства) для построения прототипа. 
\item Разработка макетов и прототипов ПИ и их оценка в деловой игре,
  выбор окончательного варианта. 
\item Имплементация ПИ в коде, создание тестовой версии. 
\item Разработка средств поддержки пользователя (пользовательские
  словари, подсказки, сообщения, помощь и пр.) и их встраивание в
  программный код. 
\item Usability тестирование тестовой версии ПИ по набору раннее
  определенных показателей. 
\item Подготовка пользовательской документации и разработка программы
  обучения. 
\end{itemize}

Эргономические цели и показатели качества программного продукта 

Приложение разрабатывается для обеспечения работы пользователя,
т.е. для того чтобы он с помощью компьютерной программы быстрее и
качественнее решал свои производственные задачи. 

С точки зрения эргономики, самое важное в программе — создать такой
пользовательский интерфейс, который сделает работу эффективной и
производительной, а также обеспечит удовлетворенность пользователя от
работы с программой. 

Эффективность работы означает обеспечение точности, функциональной
полноты и завершенности при выполнении производственных заданий на
рабочем месте пользователя. Создание ПИ должно быть нацелено на
показатели эффективности: 

Точность работы определяется тем, в какой степени произведенный
пользователем продукт (результат работы), соответствует предъявленным
к нему требованиям. Показатель точности включает процент ошибок,
которые совершил пользователь: число ошибок набора, варианты ложных
путей или ответвлений, число неправильных обращений к данным, запросов
и пр. 

Функциональная полнота отражает степень использования первичных и
обработанных данных, списка необходимых процедур обработки или
отчетов, число пропущенных технологических операций или этапов при
выполнении поставленной пользователю задачи. Этот показатель может
определяться через процент применения отдельных функций в РМ. 

Завершенность работы описывает степень исполнения производственной
задачи средним пользователем за определенный срок или период, долю
(или длину очереди) неудовлетворенных (необработанных) заявок, процент
продукции, находящейся на промежуточной стадии готовности, а также
число пользователей, которые выполнили задание в фиксированные сроки. 

Последовательность действий и набор инструментальных средств
пользователя в ПИ должны быть подчинены технологическому процессу
выполнения производственного задания. 

Не надо бояться сложности системы, надо избегать такого интерфейса,
который не соответствует алгоритму решения пользовательских задач. 

Необходимо тщательно продумать и осознать сценарий взаимодействия
программы с пользователем, приведя его к оптимальной (относительно
рассмотренных показателей) системе выполнения задач, и реализовать ПИ
в соответствии с этой системой. 

Для того, чтобы разобраться в технологии решения задач пользователя,
разработчику необходимо выяснить следующие моменты (исследуя
деятельность пользователя): 
\begin{itemize}
\item Какая информация необходима пользователю для решения задачи?
\item Какую информацию пользователь может игнорировать (не учитывать)? 
\item Совместно с пользователем разделить всю информацию на
  сигнальную, отображаемую, редактируемую, поисковую и
  результирующую. 
\item Какие решения пользователю необходимо принимать в процессе
  работы с программой? 
\item Может ли пользователь совершать несколько различных действий
  (решать несколько задач) одновременно? 
\item Какие типовые операции использует пользователь при решении задачи?
\item Что произойдет, если пользователь будет действовать не по
  предписанному Вами алгоритму, пропуская те или иные шаги или обходя
  их? 
\end{itemize}
Производительность работы отражает объем затраченных ресурсов при
выполнении задачи, как вычислительных, так и психофизиологических. 

Дизайн ПИ должен обеспечивать минимизацию усилий пользователя при
выполнении работы и приводить к: 
\begin{itemize}
\item сокращению длительности операций чтения, редактирования и поиска
  информации, 
\item уменьшению времени навигации и выбора команды,
\item повышению общей продуктивности пользователя, заключающейся в
  объеме обработанных данных за определенный период времени. 
\item увеличению длительности устойчивой работы пользователя и др. 
\end{itemize}
Сокращение непроизводственных затрат и усилий пользователя - важная
составляющая качества программного обеспечения. 

Для оценки продуктивности используются соответствующие показатели,
проверяемые специалистами по эргономике в процессе usability
тестирования рабочего прототипа. 

Формирование таких показателей происходит в процессе определения
требований к ПИ при изучении следующих вопросов: 
\begin{itemize}
\item Что от пользователя требуется в первую очередь?
\item Сколько информации, требующей обработки, поступает пользователю за период времени?
\item Каковы требования к точности и скорости ввода информации?
\item На какие операции пользователь тратит больше всего времени?
\item Чем мы можем облегчить работу пользователя при решении типовых
  задач?
\end{itemize}

Удовлетворенность пользователя от работы тесно связана с комфортностью
его взаимодействия с приложением, и способствует сохранению
профессиональных кадров на предприятии Заказчика за счет
привлекательности работы на данном рабочем месте. 

Требования к удобству и комфортности интерфейса возрастают с
увеличением сложности работ и ответственности пользователя за конечный
результат. Высокая удовлетворенность от работы достигается в случае: 
\begin{itemize}
\item Прозрачной для пользователя навигации и целевой ориентации в
  программе. Главное, чтобы было понятно, куда идем, и какую операцию
  программа после этого шага произведет. 
\item Ясности и четкости понимания пользователем текстов и значения
  икон. В программе должны быть те слова и графические образы, которые
  пользователь знает или обязан знать по характеру его работы или
  занимаемой должности. 
\item Быстроты обучения при работе с программой, для чего необходимо
  использовать преимущественно стандартные элементы взаимодействия, их
  традиционное или общепринятое их расположение. 
\item Наличия вспомогательных средств поддержки пользователя
  (поисковых, справочных, нормативных), в том числе и для принятия
  решения в неопределенной ситуации (ввод по умолчанию, обход
  <<зависания>> процессов и др.). 
\end{itemize}
Для оценки необходимого уровня удобства интерфейса также используются
специальные опросники, формуляры, чек-листы, однако к данной работе
лучше привлекать специалистов по эргономике. 

Удобный интерфейс помогает пользователю справиться с усталостью и
напряжением при работе в условиях высокой ответственности за
результат. 

Проблемы, возникающие на этапе разработки прототипа GUI и варианты их решения
\begin{enumerate}
\item Учет особенностей устройств ввода/вывода информации,
  используемых пользователем, например: 
  \begin{itemize}
  \item размер экрана монитора
  \item разрешение экрана
  \item цветовая палитра
  \item характеристики звуковой (качество воспроизведения речи) и
    видеокарты (скорость вывода при анимации) 
  \item вид мыши (с роликом или без)
  \item тип клавиатуры (“прямая”, “косая”)
  \item необходимость дополнительного оборудования (штрих-декодера,
    светового пера сенсорного экрана и др.). 
  \end{itemize}
  
\item Специфика интерактивных элементов, связанная с выбором платформы, стандартных библиотек:
  \begin{itemize}
  \item программная организация ввода/вывода информации
  \item изменение и создание новых элементов форм (контролов)
  \item приобретение нестандартных библиотек у других фирм.
  \end{itemize}

\item Выбор технологии и методов ведения диалога программы с пользователем:
  \begin{itemize}
  \item степень активности пользователя при взаимодействии
    (автоматический режим или перехват управления программой на себя,
    визарды, обеспечение доступа ко всем средствам интерфейса
    независимо от действий пользователя) 
  \item степень учета ситуации (контекстные подсказки, меню дальнейших
    событий или объектов, запоминание типичных путей диалога) 
  \item соответствие ожиданиям пользователя (предсказание,
    предобработка, предформатирование) 
  \item устойчивость, терпимость к ошибкам пользователя путем
    исправления типичных ошибок 
  \item дублирование вручную отдельных функций системы и
    дополнительные контрольные процедуры работы отдельных режимов 
  \item настройка ПИ на различный уровень подготовки пользователя
    (образность или метафоричность предметной области в противовес
    сокращениям и горячим клавишам) 
  \item степень адаптивности ПИ под предпочтения пользователя
    (изменение способа и порядка отображения, перекомпоновка экрана,
    выбор отдельных характеристик (стиля) и пр.) 
  \item настройка ПИ на специфику задачи (новый формат данных,
    изменение набора объектов, дополнение атрибутов объектов) 
  \end{itemize}

\item Размещение информации и управляющих элементов в поле экрана, в
  окне. При композиции экрана необходимо учитывать ограниченные
  размеры пространства экрана, в связи с чем возникает задача
  оптимального расположения максимально возможного объема информации
  путем: 
  \begin{itemize}
  \item логической увязкой данных в зависимости от алгоритма работы
    пользователя, а не ориентацией на структуру и последовательность
    физических таблиц данных 
  \item определения уровня “детальности – обобщенности” вывода
    информации (нахождение компромисса между желанием вывести много
    записей одновременно и/или сразу увидеть детальную информацию по
    каждой из них) 
  \item выделения важной информации на экране 
  \item четкого определения основных и вспомогательных блоков
    информации 
  \item определения статических полей на экране, а также полей, где
    информация периодически изменяется 
  \item избегания перекрывающихся окон на экране 
  \item применения принципов гармонии при компоновке экрана
    (симметрия, баланса масс, соблюдение пропорций, сочетание цветов) 
  \end{itemize}
\item Формирование обратной связи между пользователем и приложением: 
  \begin{itemize}
  \item показ актуального состояния системы, режима работы системы
    (автономного, штатного, защищенного и пр.) и режима взаимодействия
    (например, отображение, редактирование или поиск данных). 
  \item вывод отдельных, важных для рабочей операции данных и
    показателей 
  \item отражение действий пользователя (нажатия клавиш, запуск
    процесса, динамика выполнения процесса, получение ожидаемого и
    иного результата) 
  \item ясность и информативность сообщений системы.
  \end{itemize}
\item Проектирование панелей меню и инструментов (toolbars) и выбор пунктов в них:
  \begin{itemize}
  \item логическая и смысловая группировка пунктов
  \item фиксированная позиция панелей на экране
  \item ограничение на ширину списка выборов и шагов (глубины) меню 
  \item использование привычных названий, широко распространенных
    икон-пиктограмм, традиционных икон-символов и аккуратное введение
    сокращений 
  \item размещение наиболее часто используемых пунктов (обычно в
    начале списка). 
  \end{itemize}
\item Разработка средств ориентации и навигации:
  \begin{itemize}
  \item легкость определения своего местонахождения и указание
    направления следования 
  \item удобный переход от обобщенного взгляда до конкретных деталей
    (варьирование степени детализации рассматриваемых объектов) 
  \item быстрый поиск в списке или таблице
  \item указание на дополнительно существующую информацию и способ ее
    получения 
  \item использование средств листания и прокрутки.
  \end{itemize}
\item Создание форм для ввода данных:
  \begin{itemize}
  \item использования одного или нескольких механизмов ввода в рамках
    режима (клавиатура, мышь, штрих-декодер, световое перо, др.) 
  \item определение способов ввода данных (таблицы, списки, простая форма, меню и пр.)
  \item минимизация объема ввода
  \item выделение редактируемых обязательных и необязательных, а также нередактируемых полей
  \item использование механизмов быстрого ввода (по умолчанию, сокращения, с продолжением и пр.)
  \item Выделение введенной или отредактированной информации.
  \end{itemize}
\end{enumerate}

Принципы реализации пользовательского интерфейса:

\emph{Стилевая гибкость} - 
возможность использовать различные интерфейсы с одним и тем же
приложением, на практике реализуется в виде набора “skins”, для
web-интерфейсов – с помощью таблицы стилей, в том числе возможность в
выборе пользователем собственных установок ПИ (цвет, иконы, подсказки
и пр.). 

\emph{Совместное наращивание функциональности} - 
возможность развивать приложение без разрушения (т.е. оставаясь в
рамках) существующего интерфейса. 

\emph{Масштабируемость} - 
возможность легко настраивать и расширять как интерфейс, так и само
приложение при увеличении числа пользователей, рабочих мест, объема и
характеристик данных. 

\emph{Адаптивность к действиям пользователя} - 
приложение должно допускать возможность ввода данных и команд
множеством разных способов (клавиатура, мышь, другие устройства) и
многовариативность доступа к прикладным функциям (иконы, <<горячие
  клавиши>>, меню …), кроме того программа должна учитывать возможность
перехода и возврат от окна к окну, от режима к режиму, и правильно
обрабатывать такие ситуации.

\emph{Независимость в ресурсах} - 
для создания пользовательского интерфейса должны предоставляться
отдельные ресурсы, направленные на хранение и обработку данных,
необходимых для поддержки пользователя (пользовательские словари,
контекстно-зависимые списки, наборы данных по умолчанию или по
последнему запросу, истории запросов и пр.)

\emph{Переносимость} - 
при переходе на другую аппаратную (программную) платформу, должен
осуществляется автоматически перенос и пользовательского интерфейса, и
конечного приложения. 
\end{document}
